package tk0084.dev.google.quiz.lite;

import it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap;

import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.PreparedStatement;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.Stack;
import java.util.TreeMap;
import java.util.WeakHashMap;

import javax.management.RuntimeErrorException;

public class DfsPuzzle implements PuzzleStrategy {

	private Puzzle _puzzle;
	private boolean _isUnpuzzled;

	private Integer _depthLimit = DEFAULT_DEPTH_LIMIT;
	public static Integer DEFAULT_DEPTH_LIMIT = 1;
//	public static Integer MAX_DEPTH_LIMIT = 33;
	public static Integer MAX_DEPTH_LIMIT = 40;
	public static Integer DEPTH_LIMIT_AMP = 2;

	private int MAX_CACHE_SIZE = 7000000;
	private Map<Integer, Integer> _visited = new WeakHashMap<Integer, Integer>();
//	private Int2IntOpenHashMap _visited = new Int2IntOpenHashMap();
	private Stack<Operation> _unpuzzledOperations = new Stack<Operation>();
	private Stack<Operation> _currentOperations = new Stack<Operation>();
	private Stack<Integer> _visitedState = new Stack<Integer>();

	
	private StateCache _stateCache;

	public DfsPuzzle() {
		// try {
		// _stateCache = new StateCache();
		// } catch (ClassNotFoundException e) {
		// e.printStackTrace();
		// } catch (SQLException e) {
		// e.printStackTrace();
		// }
	}

	public String unpuzzle(final Puzzle puzzle) {
		_puzzle = puzzle;
//		for (_depthLimit = _puzzle.getMd() - 1; _depthLimit < MAX_DEPTH_LIMIT; _depthLimit += DEPTH_LIMIT_AMP) {
		for (_depthLimit = 30; _depthLimit < MAX_DEPTH_LIMIT; _depthLimit += DEPTH_LIMIT_AMP) {
			// System.out.println("limit:" + _depthLimit);

			doUnpuzzle(_puzzle.getInitialChars().toCharArray());

			_currentOperations.clear();
			_visited.clear();
			
			if (_isUnpuzzled) {
				return printHistory();
			}
			
			// _stateCache.clear();
		}

		return "";
	}

	private void doUnpuzzle(char[] stateChars) {

		if (_currentOperations.size() > _depthLimit) {
			return;
		}

		if(_isUnpuzzled && _currentOperations.size() > _unpuzzledOperations.size()){
			return;
		}
		
		final int stateHash = State.getStateHashCode(stateChars);
//		final int oldVisitStateOrder = _visited.get(stateHash);
		final Integer oldVisitStateOrder = _visited.get(stateHash);
		
//		if (oldVisitStateOrder != 0 && oldVisitStateOrder <= _currentOperations.size()) {
		if (oldVisitStateOrder != null && oldVisitStateOrder <= _currentOperations.size()) {
			return;
		} else {
			if (_visited.size() < MAX_CACHE_SIZE) {
				_visited.put(stateHash, _currentOperations.size());
			}else{
//				System.out.print("oc ");
			}
		}

		if (_puzzle.isEndState(stateChars)) {

			registerEndState();

		} else {

			move(stateChars, _puzzle.getRow(), _puzzle.getCol());
//			final Table table = new Table(stateChars, _puzzle.getRow(), _puzzle.getCol());
//			final Operation lastOp = _currentOperations.isEmpty() ? null : _currentOperations.lastElement();
//
//			if (table.canUp() && lastOp != Operation.DOWN) {
//				char[] moveTo = table.moveUp();
//				_currentOperations.add(Operation.UP);
//				doUnpuzzle(moveTo);
//				table.restore();
//				_currentOperations.pop();
//			}
//
//			if (table.canRight() && lastOp != Operation.LEFT) {
//				char[] moveTo = table.moveRight();
//				_currentOperations.add(Operation.RIGHT);
//				doUnpuzzle(moveTo);
//				table.restore();
//				_currentOperations.pop();
//			}
//
//			if (table.canDown() && lastOp != Operation.UP) {
//				char[] moveTo = table.moveDown();
//				_currentOperations.add(Operation.DOWN);
//				doUnpuzzle(moveTo);
//				table.restore();
//				_currentOperations.pop();
//			}
//
//			if (table.canLeft() && lastOp != Operation.RIGHT) {
//				char[] moveTo = table.moveLeft();
//				_currentOperations.add(Operation.LEFT);
//				doUnpuzzle(moveTo);
//				table.restore();
//				_currentOperations.pop();
//			}
		}
	}

	public String printHistory() {
		StringBuilder sb = new StringBuilder();
		for (Operation op : _unpuzzledOperations) {
			sb.append(op);
		}
		return sb.toString();
	}

	public void move(char[] chars, final int row, final int col){
		final Operation lastOp = _currentOperations.isEmpty() ? null : _currentOperations.lastElement();

		final int emptyIndex = StaticTable.getEmptyIndex(chars) ;
		
		if (StaticTable.canUp(chars, row, col, emptyIndex) && lastOp != Operation.DOWN) {
			char[] moveTo = StaticTable.moveUp(chars, row, col, emptyIndex);
			_currentOperations.add(Operation.UP);
			doUnpuzzle(moveTo);
			StaticTable.restore(chars, row, col, emptyIndex);
			_currentOperations.pop();
		}

		if (StaticTable.canRight(chars, row, col, emptyIndex) && lastOp != Operation.LEFT) {
			char[] moveTo = StaticTable.moveRight(chars, row, col, emptyIndex);
			_currentOperations.add(Operation.RIGHT);
			doUnpuzzle(moveTo);
			StaticTable.restore(chars, row, col, emptyIndex);
			_currentOperations.pop();
		}

		if (StaticTable.canDown(chars, row, col, emptyIndex) && lastOp != Operation.UP) {
			char[] moveTo = StaticTable.moveDown(chars, row, col, emptyIndex);
			_currentOperations.add(Operation.DOWN);
			doUnpuzzle(moveTo);
			StaticTable.restore(chars, row, col, emptyIndex);
			_currentOperations.pop();
		}

		if (StaticTable.canLeft(chars, row, col, emptyIndex) && lastOp != Operation.RIGHT) {
			char[] moveTo = StaticTable.moveLeft(chars, row, col, emptyIndex);
			_currentOperations.add(Operation.LEFT);
			doUnpuzzle(moveTo);
			StaticTable.restore(chars, row, col, emptyIndex);
			_currentOperations.pop();
		}
	}
	
	/*------------------------------------------------
	 * private
	 * ------------------------------------------------
	 */
	class StateCache {

		Connection _connection;
		PreparedStatement _setCachePs;
		PreparedStatement _getCachePs;
		PreparedStatement _truncatePs;

		StateCache() throws ClassNotFoundException, SQLException {
			_connection = DataSource.getConnection();
			_setCachePs = _connection.prepareStatement("insert into state values(?)");
			_getCachePs = _connection.prepareStatement("select 1 from state where state_id = ? limit 1");
			_truncatePs = _connection.prepareStatement("TRUNCATE TABLE STATE");
		}

		void set(int stateHash) throws SQLException {
			_setCachePs.setInt(1, stateHash);
			_setCachePs.execute();
		}

		boolean get(int stateHash) throws SQLException {
			_getCachePs.setInt(1, stateHash);
			ResultSet rs = _getCachePs.executeQuery();
			return rs.next();
		}

		void clear() throws SQLException {
			_truncatePs.execute();
		}

		void close() throws SQLException {
			_connection.close();
		}
	}

	private void registerEndState() {

		if (_unpuzzledOperations.isEmpty() || _currentOperations.size() < _unpuzzledOperations.size()) {
			_unpuzzledOperations = (Stack<Operation>) _currentOperations.clone();

			System.out.println("end state found :" + printHistory());

			// TODO
			_depthLimit = _unpuzzledOperations.size();

			_isUnpuzzled = true;
		}
	}

}
